package com.freedy.algorithm.kruskal;


import java.util.ArrayList;

/**
 * 创建最小生成树->村庄的图
 *
 * @author Freedy
 * @date 2021/4/13 21:58
 */
public class MinTree {
    private final MGraph graph;

    public MinTree(MGraph graph) {
        this.graph = graph;
    }

    public void createMinTree() {
        System.out.println("生成最小生成树");
        //保存已被访问的点（就是已经生成的最小生成树）的下个点
        int[] ends=new int[graph.getEdgeNum()];
        //创建结果数组
        ArrayList<MGraph.Edge> edges = graph.getEdges();
        //遍历edges，将最小边添加到结果数组中，如果构成回路则不添加
        for (MGraph.Edge edge : edges) {
            int start = edge.getStart();
            int end = edge.getEnd();
            //获取start在已有最小生成树中的终点
            int m = graph.getEnd(ends, start);
            int n = graph.getEnd(ends, end);
            //没有构成回路
            if (m != n) {
                //设置终点
                ends[m] = n;
                //打印最小生成树
                System.out.println(edge);
            }
        }
    }
}
